'''
Created on Jan 11, 2013

@author: netzer
'''

from Quoridor_game import WHITE, TIE, DIRECTIONS, GetNextLocation
from utils import FIFOQueue


def AlphaBetaShitUtility(self, state):
        winner = state.getWinner()
        if winner is None:
            whiteDistance = 0
            for posW in state.locationsW:
                if posW != None: 
                    whiteDistance += (state.brdSize - 1 - posW[0])
                    whiteDistance += (posW[1] / 10.0)
            
            blackDistance = 0
            for posB in state.locationsB:
                if posB != None: 
                    blackDistance += posB[0]
                    blackDistance += (posB[1] / 10.0) 
            
            utilityValW = blackDistance - whiteDistance
            if self.player == WHITE:
                return utilityValW
            else:
                return -utilityValW            
            
        elif winner == self.player:
            return 100000
        elif winner == TIE:
            return 0
        else:
            return -100000

def centeredUtility(self, state):
    winner = state.getWinner()
    whiteXDistance = 0
    blackXDistance = 0
    if winner is None:
        for posW in state.locationsW:
            if posW != None: 
                whiteXDistance += abs(posW[1]-state.brdSize/2)
        
        for posB in state.locationsB:
            if posB != None: 
                blackXDistance += abs(posB[1]-state.brdSize/2)
        
        utilityValW = blackXDistance - whiteXDistance
        if self.player == WHITE:
            return utilityValW
        else:
            return -utilityValW            
        
    elif winner == self.player:
        return 100000
    elif winner == TIE:
        return 0
    else:
        return -100000
        
def fewRowsUtility(self, state):
        winner = state.getWinner()
        if winner is None:
            whiteRowsFromDest = 0
            for posW in state.locationsW:
                if posW != None: 
                    whiteRowsFromDest += (state.brdSize - 1 - posW[0])
            
            blackRowsFromDest = 0
            for posB in state.locationsB:
                if posB != None: 
                    blackRowsFromDest += posB[0]
            
            utilityValW = whiteRowsFromDest
            utilityValB = blackRowsFromDest
            utilRes = utilityValB - utilityValW
#            print 'white rows from dest ',whiteRowsFromDest
#            print 'black rows from dest ',blackRowsFromDest
            if self.player == WHITE:
                return utilRes
            else:
                return -utilRes            
            
        elif winner == self.player:
            return 100000
        elif winner == TIE:
            return 0
        else:
            return -100000
        
def willToWinUtility(self, state):
        winner = state.getWinner()
        if winner is None:
            whiteWillToNextRow = 0
            for posW in state.locationsW:
                if posW != None: 
                    whiteWillToNextRow += pow(posW[0],1.3)
            
            blackWillToNextRow = 0
            for posB in state.locationsB:
                if posB != None: 
                    blackWillToNextRow += pow((state.brdSize - 1 - posB[0]),1.3)
            
            utilityValW = whiteWillToNextRow
            utilityValB = blackWillToNextRow
            utilRes = utilityValW - utilityValB
            if self.player == WHITE:
                return utilRes
            else:
                return -utilRes            
            
        elif winner == self.player:
            return 100000
        elif winner == TIE:
            return 0
        else:
            return -100000
        
def shortestWayUtility(self, state):
        '''
        finds the shortest way to a certain row using BFS algo
        '''
        def addChildrenToQeueu(queue, pos):
            '''
            giving a position appending children positions to the queue
            '''
            for dir in DIRECTIONS:
                nextLoc = GetNextLocation(pos, dir)
                if nextLoc[0] < 0 or nextLoc[0] >= state.brdSize or nextLoc[1] < 0 or nextLoc[1] >= state.brdSize:
                    continue
                if visitingMap[nextLoc[0]][nextLoc[1]] == 1:
                    continue
                if not state._moveOkByWalls(dir, nextLoc[0], nextLoc[1]):
                    continue
                visitingMap[nextLoc[0]][nextLoc[1]] = 1
                queue.append(nextLoc)
        
        def LimitedBFSStateSearch(q,pos,targetRow):
            '''
            BFS searching for the shortest path
            '''
#            start = time.clock()
            pathLength = 0
            iterateLimit = 3
            q.append(pos)
            if targetRow == pos[0]:
                return pathLength
            while q != None and len(q) > 0 and iterateLimit > 0:
                qLen =  range(len(q))
                for i in qLen:
                    currPos = q.pop()
                    if targetRow == currPos[0]:
                        q = None
                        break
                    addChildrenToQeueu(q,currPos)
                pathLength += 1
                iterateLimit -= 1
#            print "BFS duration ", time.clock()-start
            return pathLength
        
        visitingMap =  [ [ 0 for i in range(state.brdSize) ] for i in range(state.brdSize) ]
        rowsFromPos = 1        
        whitePathLength = 0
        blackPathLength = 0
        winner = state.getWinner()
        if winner is None:
            
            que = FIFOQueue()
            for pos in state.locationsW:
                if pos == None:
                    continue
                targetRow = min(pos[0] + rowsFromPos,state.brdSize - 1) 
    #                BFS search for each piece finding the shortest way
                whitePathLength += LimitedBFSStateSearch(que,pos,targetRow)
                    
            que = FIFOQueue()      

            for pos in state.locationsB:
                if pos == None:
                    continue
                targetRow = max(pos[0] - rowsFromPos,0)                 
    #                BFS search for each piece finding the shortest way
                blackPathLength += LimitedBFSStateSearch(que,pos,targetRow)
                
            utilityW = blackPathLength - whitePathLength
            if self.player == WHITE:
                return utilityW
            else:
                return -(utilityW)             
                        
        elif winner == self.player:
            return 100000
        elif winner == TIE:
            return 0
        else:
            return -100000
        

def mostWallsLeftUtility(self, state):
        winner = state.getWinner()
        if winner is None:
            value = state.WallsLeftW - state.WallsLeftB
            return (self.player == WHITE and value ) or -value
        
        elif winner == self.player:
            return 100000
        elif winner == TIE:
            return 0
        else:
            return -100000


def trickOppUtility(self, state):
    winnerMe = state.getWinner()
    winnerHim = state.father.getWinner()
    
    if winnerMe is None and winnerHim is None:
        return willToWinUtility(self,state) - willToWinUtility(self,state.father)
       
    return 0;
#    if winnerHim  is None :
#        return -100000
#    elif winnerHim == TIE:
#        return 0
#    else:
#        return 100000
#    
#    if winnerMe == self.player:
#        return 100000
#    elif winnerMe == TIE:
#        return 0
#    else:
#        return -100000
    
    
    
        
    
UTILITIES = [willToWinUtility, mostWallsLeftUtility,shortestWayUtility]